// https://zhuanlan.zhihu.com/p/446622823

function accountsMerge(accounts) {
    let rowLen = accounts.length
    let emailNameMap = new Map()
    let emailIndexMap = new Map()
    
    // 初始化每一个账号为一个团队
    let emailIndex = 0
    for(let row=0; row<rowLen; row++){
        let name = accounts[row][0]
        let colLen = accounts[row].length
        for(let col=1; col<colLen; col++){
            let email = accounts[row][col]
            console.log(email)
            if(!emailIndexMap.has(email)){
                emailIndexMap.set(email, emailIndex++)
                emailNameMap.set(email, name)
            }
        }
    }
    console.log(emailIndexMap)
    let uf = new UnionFind(emailIndex)
   // 将同一个人对应的邮箱合并
   for(let row=0; row<rowLen; row++){
    let colLen = accounts[row].length
    let firstEmail = accounts[row][1]
    let firstIndex = emailIndexMap.get(firstEmail)
    for(let col=2; col<colLen; col++){
        let nextEmail = accounts[row][col]
        let nextIndex = emailIndexMap.get(nextEmail)
        uf.union(firstIndex, nextIndex)
    }
   }
   console.log(uf)
   const indexToEmailMap = new Map()
   for (const [email, index] of emailIndexMap) {
       let indexRoot = uf.find(index)
       console.log(email, index ,indexRoot)
       let emails = [email]
       if(indexToEmailMap.has(indexRoot)){
            indexToEmailMap.get(indexRoot).forEach(element => {
                emails.push(element)
           });
       }
       indexToEmailMap.set(indexRoot,emails )
   }
   const mergeArr = []
   for (const [index, emails] of indexToEmailMap) {
     emails.sort()
     let name = emailNameMap.get(emails[0])
     const newArr = []
     newArr.push(name)
     newArr.concat(emails)
     emails.forEach(email => {
        newArr.push(email)
     });
     mergeArr.push(newArr)
       
   }
   console.log(mergeArr)
   return mergeArr
}
   

   class UnionFind {
       constructor(capacity){
         this.parent = new Array(capacity)
         this.rank = new Array(capacity)
         for(let i=0; i<capacity; i++){
             this.parent[i] = i
             this.rank[i] = i
         }
       }

       find(x){
        if(x < 0 || x >= this.parent.length){
            throw new TypeError('x 超出了范围')
        }
        while(x != this.parent[x]){
            this.parent[x] = this.parent[this.parent[x]] // 路径压缩
            x = this.parent[x]
        }
        return x
     }

     union(x, y){
        let fx = this.find(x)
        let fy = this.find(y)
        if(fx == fy) return 
        console.log(x, y, fx, fy)
        if(this.rank[fx] < this.rank[fy]){
            this.parent[fx] = fy
        }else if(this.rank[fx] > this.rank[fy]){
            this.parent[fy] = fx
        }else{
            this.parent[fy] = fx
            this.rank[fx] += 1
        }
    }
   }

    
    



// let accounts = [
//     ["Lily","Lily4@m.co","Lily5@m.co"],
//     ["Lily","Lily8@m.co","Lily9@m.co"],
//     ["Lily","Lily15@m.co","Lily16@m.co"],
//     ["Lily","Lily19@m.co","Lily20@m.co"],
//     ["Lily","Lily6@m.co","Lily7@m.co"],
//     ["Lily","Lily10@m.co","Lily11@m.co"],
//     ["Lily","Lily5@m.co","Lily6@m.co"],
//     ["Lily","Lily13@m.co","Lily14@m.co"],
//     ["Lily","Lily9@m.co","Lily10@m.co"],
//     ["Lily","Lily1@m.co","Lily2@m.co"],
//     ["Lily","Lily3@m.co","Lily4@m.co"],
//     ["Lily","Lily2@m.co","Lily3@m.co"],
//     ["Lily","Lily11@m.co","Lily12@m.co"],
//     ["Lily","Lily7@m.co","Lily8@m.co"],
//     ["Lily","Lily12@m.co","Lily13@m.co"],
//     ["Lily","Lily18@m.co","Lily19@m.co"],
//     ["Lily","Lily17@m.co","Lily18@m.co"],
//     ["Lily","Lily16@m.co","Lily17@m.co"],
//     ["Lily","Lily14@m.co","Lily15@m.co"],
// ["Lily","Lily0@m.co","Lily1@m.co"]]

//accountsMerge(accounts)


accounts = [
["David","David0@m.co","David5@m.co","David0@m.co"],
["Lily","Lily4@m.co","Lily2@m.co","Lily0@m.co"],
["Fern","Fern5@m.co","Fern2@m.co","Fern6@m.co"],
["Gabe","Gabe0@m.co","Gabe6@m.co","Gabe8@m.co"],
["Alex","Alex7@m.co","Alex5@m.co","Alex7@m.co"],
["Lily","Lily4@m.co","Lily6@m.co","Lily7@m.co"],
["Alex","Alex0@m.co","Alex4@m.co","Alex5@m.co"],
["John","John4@m.co","John2@m.co","John0@m.co"]
]

accountsMerge(accounts)

